import java.util.Arrays;

public class Solution {
    public int deleteAndEarn(int[] nums) {
        //类似于打家劫舍II
        //由于nums[i] - 1、nums[i] + 1与nums[i]是相邻的，即相当于一个房间的相邻两个房间不能进去
        //nums中的元素表示房间号

        int len = nums.length;

        Arrays.sort(nums);

        int max = nums[len - 1];//nums中的最大值

        int[] arr = new int[max + 1];//下标表示nums中的元素，值表示nums中该元素出现的次数

        for (int num : nums) {
            arr[num]++;
        }

        int[] f = new int[max + 1];
        int[] g = new int[max + 1];

        f[1] = arr[1] * 1;

        for (int i = 2; i < max + 1; i++) {
            f[i] = g[i - 1] + i * arr[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        return Math.max(f[max], g[max]);
    }
}
